A first course in CCT usually defines and explores many discrete objects, and the basic theorems largely use combinatorial reasoning. Over the years, there has been a very definitive influx of algebraic thinking (algebraic geometry, commutative algebra, representation theory, etc.) into CCT. This course shall attempt to go over some of the main avenues for algebraic thought in CCT. The broad plan would be to cover the following:
1) I want (any potential) computer science students to be introduced to the many powerful abstract algebraic tools that are permeating CCT,
2) I want pure math students to be exposed to the many profound and fiendishly difficult problems in CCT where algebraic methods can provide insights.
I'd be very grateful if interested people could send me emails in advance informing me of their background, so I can gauge how much background material I need to prepare.
Before each lecture, I will mention (well in advance) what you need to be familiar with to follow the lecture. I will also post resources which will help you gain familiarity. Not only that, I am most happy to engage with you outside class to discuss those concepts and help you. During the actual class, I might give brief introductions to those concepts, but can make no promise about it. It would be best if you are prepared that I will assume familiarity with those concepts.
|
Full notes |
| Date | Prerequisites | Topics | Notes | Post lecture remarks |
|---|---|---|---|---|
| Week 1 (May 3) | general mathematical maturity, asymptotic notation | logistics, computational complexity theory basics (define P vs NP, VP vs VNP), overview of upcoming topics -- matrix multiplication, determinantal complexity bounds, connections to fewnomial bounds, geometric complexity theory, Ulrich complexity, very brief mention of misc. topics (decision tree complexity bounds, "rising sea" approaches in complexity theory -- categorical complexity (Basu-Isik), and complexity theory of constructible sheaves (Basu), Freedman's proof of existence of certain types of knots using complexity conjectures) | Couldn't do a proper overview of GCT, Ulrich complexity, and other misc. topics. Plan to do in next lecture. | |
| Week 2 (May 10) | basic linear algebra, tensors, tensor rank, basic group theory and representation theory. See this for an excellent light introduction to tensors, and this (at least up to Section 1.3) for a little more on tensors. | finish overview of topics, complexity of matrix multiplication -- very brief intro. to tensors, "conceptual" understanding of Strassen's method (Grochow-Moore), border rank, ideas behind stronger lower bounds, upper bounds (Bini, Schonhage, brief mention of Coppersmith-Winograd, Cohn-Umans group theoretic approach of embedding matrix multiplication into semi-simple algebras) | Couldn't do border rank onwards. Postponed to next lecture. | |
| Week 3 (May 17) | basic linear algebra, tensors, tensor rank, basic group theory and representation theory. See this for an excellent light introduction to tensors, and this (at least up to Section 1.3) for a little more on tensors. | finish - border rank, ideas behind stronger lower bounds, upper bounds (Bini, Schonhage, brief mention of Coppersmith-Winograd, Cohn-Umans group theoretic approach of embedding matrix multiplication into semi-simple algebras) | Couldn't do Cohn-Umans. Postponed to next lecture. | |
| Week 4 (May 24) | basic group theory and representation theory | finish Cohn-Umans group theoretic approach of embedding matrix multiplication into semi-simple algebras (talk about association schemes as well), algebraic complexity basics -- circuits, defns of VP and VNP, determinantal complexity | Defined VP, VNP. Proved perm is in VNP. Will do some more basics of algebraic complexity and bounds on determinantal complexity in the next lecture. | |
| Week 5 (May 31) | basics of projective space and projective varieties (e.g. Chapter 8 of Ideals, Varieties and Algorithms of Cox et al.), basic differential geometry (e.g. Introductory chapters of Differential Geometry of Curves and Surfaces by do Carmo or first few pages of this online book) and algebraic geometry (e.g. Notes of Gathmann) | basics of algebraic complexity theory, determinantal complexity (dc), Mignon-Ressayre's lower bound on dc of permanent (define Gauss maps in terms of conormal lines, degeneracy of Gauss images, obtain bound by dimension count), Grenet's upper bound on dc of permanent | Finished up to showing non-degeneracy of the dual variety of the permanent hypersurface. Will finish lower bound proof and upper bound proof in the next lecture. | |
| Week 6 (Jun 7) | exterior product (e.g. this), Koszul complexes (this and/or this are reasonably easy to read references) | establish degeneracy of the Gauss image of the determinant hypersurface to prove Mignon-Ressayre's lower bound, explain Grenet's upper bound both combinatorially and in terms of the Koszul complex, equivariance of Grenet's representation and exponential separation b/w perm and det under the restriction of equivariance, other restricted models of computation (Waring rank), depth 3,4,5 circuits and connections to the secant varieties of the Veronese and Chow varieties, the result of Gupta et al. on size of restricted depth 4 circuits computing the permanent by studying Hilbert functions of Jacobian ideals (the method of shifted partial derivatives), fewnomials and the real-tau conjecture, an approach to the real-tau conjecture using the Wronskian determinant | Surprisingly finished everything I wanted to! | |
| Week 7 (Jun 14) | basic differential geometry (e.g. first three chapters of this), basic notions from commutative algebra, algebraic geometry and representation theory (for representation theory, see for example first 12 pages of this) | Ulrich complexity (definition in terms of Ulrich bundles, implication to VP vs VNP), Geometric Complextity Theory (introduction, border complexity and orbit closures, how representation theory helps (look at multiplicities of irreps), stability, Luna's etale slice theorem, partial stability, characterization by symmetries, P vs NP in GCT) | Did introduce GCT, spoke about importance of orbit closures and representation theory, but could not get into stability and more. Will finish in next lecture. | |
| Week 8 (Jun 21) | basic notions from group theory, algebraic geometry and representation theory (for representation theory, see for example first 12 pages of this) | Geometric Complextity Theory (stability, Luna's etale slice theorem, partial stability, characterization by symmetries, separating orbit closures with multiplicities, NP vs P/poly in GCT), brief mentions of a medley of topics -- hardness of approximation and Unique games conjecture (connection to homology localization as well), Betti numbers for lower bounds on decision/computation trees, categorical complexity (complexity using colimit computations), Freedman's result on existence of certain types of knots, etc. | Didn't do miscellaneous topics, but finished GCT! |
For those of you who are taking this course for credit, after each class, you will be required to send a short email to me recording three things that stood out to you. This is based upon Ravi Vakil's note about how even someone who is completely at sea at a talk can end up improving their mathematical knowledge after all.
The idea is that during the lecture, you record three things (e.g definitions, theorems, themes, examples, questions) that stood out to you. They should be things you have not encountered previously (if none exist, just choose your most favourite things). If unknown to you, look up these things in whatever sources you find, read about them, and try to internalize them to some extent. Your email should name the three things, and also comment on those things. Your comments should reflect your personal understanding/interpretation. Don't just state definitions.
I don't want to put a mandate such as a minimum number of words per concept. I will trust that you will be conscientious and do the exercise seriously, and comment on the concepts meaningfully.